/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 实现 strStr()
 */

// @lc code=start
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        //haystack找出needle出现的第一个位置
        if (needle == "")
        {
            return 0;
        }
        //sunday算法第一次实现
        //偏移表 如果字符在pattern出现 偏移为在pattern中出现的最右位置到尾部的距离+1
        //否则偏移为 pattern长度+1
        //如果字符串匹配 返回 否则找到末尾的下一个字符 如果在pattern中 查偏移表
        unordered_map<char, int> a;
        //偏移表赋值
        int hsize = haystack.size();
        int nsize = needle.size();
        for (int i = 0; i < nsize; i++)
        {
            a[needle[i]] = nsize - i;
        }
        int index = 0; //待匹配字符串的第一个字符位置
        while (index <= hsize - nsize)
        {
            if (haystack.substr(index, nsize) == needle)
            {
                return index;
            }
            else
            {
                if (index + nsize > hsize - 1)
                {
                    return -1;
                }
                else
                {
                    //查找偏移值
                    if (a.find(haystack[index + nsize]) != a.end())
                    {
                        index += a[haystack[index + nsize]];
                    }
                    else
                    {
                        index += nsize + 1;
                    }
                }
            }
        }
        return -1;
    }
};
// @lc code=end
